package com.LeeCode;

import java.util.HashSet;
import java.util.Set;

/**
 * 检查一个字符串是否包含所有长度为 K 的二进制子串
 */

public class Code1461 {
    public static void main(String[] args) {
        String s = "00110110";
        int k = 2;
        System.out.println(new Code1461().hasAllCodes(s, k));
    }

    public boolean hasAllCodes(String s, int k) {
        if (s.length() < (1 << k) + k - 1) {
            return false;
        }

        int num = Integer.parseInt(s.substring(0, k), 2);
        Set<Integer> exists = new HashSet<Integer>();
        exists.add(num);

        for (int i = 1; i + k <= s.length(); ++i) {
            num = (num - ((s.charAt(i - 1) - '0') << (k - 1))) * 2 + (s.charAt(i + k - 1) - '0');
            exists.add(num);
        }
        return exists.size() == (1 << k);
    }
}
